# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 22_bitmap.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/2/21 16:20
------------------------------------------
    位图算法，
        主要用于对大量整数做去重和查询操作
        优势：高性能的位运算
"""


class Bitmap:
    def __init__(self, size):
        self.words = [0] * (self.get_word_index(size - 1) + 1)
        self.size = size

    def get_bit(self, bit_index):
        if bit_index < 0 or bit_index > self.size - 1:
            raise Exception("超过Bitmap有效范围")

        word_index = self.get_word_index(bit_index)
        return (self.words[word_index] & (1 << bit_index)) != 0

    def set_bit(self, bit_index):
        if bit_index < 0 or bit_index > self.size - 1:
            raise Exception("超过Bitmap有效范围！")

        word_index = self.get_word_index(bit_index)
        self.words[word_index] |= (1 << bit_index)

    @staticmethod
    def get_word_index(bit_index):
        # 右移6位，相当于除以64
        return bit_index >> 6


def demo():
    bitmap = Bitmap(128)
    bitmap.set_bit(64)
    bitmap.set_bit(75)
    print(bitmap.get_bit(126))
    print(bitmap.get_bit(78))


if __name__ == '__main__':
    demo()
